Investigating Second Eigenvalue

  if (require("PageRank")) {
      library(PageRank)
    }else{
      devtools::install_github("ryangreenup/PageRank")
      library(PageRank)
    }

  library(pacman)
  pacman::p_load(PageRank, devtools, Matrix, igraph, mise, tidyverse, rgl, latex2exp)
#  mise()

Looking at Density

Constants

Define some constants

n <- 20
p <- 1:n/n
beta <- 1:n/n
beta <- runif(n)*100
#sz <- 1:n/n+10
sz <- (1:n/n)*100+10
input_var <- expand.grid("n" = n, "p" = p, "beta" = beta, "size" = sz)
input_var

Function to Build Graph

random_graph <- function(n, p, beta, size) {
      g1 <- igraph::erdos.renyi.game(n = sz, p)
      A <- igraph::get.adjacency(g1) # Row to column
      A <- Matrix::t(A)

      A_dens <- mean(A)
      T      <- PageRank::power_walk_prob_trans(A)
      tr     <- sum(diag(T))
      e2     <- eigen(T, only.values = TRUE)$values[2] # R orders by descending magnitude
      A_det  <- det(T)
      return(c(abs(e2), A_dens, A_det, tr))
}

Return results

Map the function

Plot Results


chival <- dchisq(seq(from = 0, to = 40, length.out = 100), df = 10)*7
index  <- seq(from = 0, to = 2.2, length.out = 100)
chidata  <- data.frame(index = index, chi = chival)
ggplot(data) +
  geom_point(mapping = aes(x = density, y = eigenvalue2, size = beta, color = size, shape = factor(n))) +
  scale_size_continuous(range = c(0.1,1)) +
  labs(x = "Density of Adjacency Matrix", y = TeX("$\\xi_2$ of $T_{PW}$"))

mod <- lm(eigenvalue2 ~ poly(density, 1), data = data)
mod$residuals %>%  hist(breaks = 90)

hist(rnorm(3000), breaks = 100)

plot(mod)

NA

This is interesting, lets look at a snapshot of it:

library(scatterplot3d)
shapes = c(16, 17, 18) 
shapes <- shapes[as.numeric(iris$Species)]
scatterplot3d(iris[,1:3], pch = shapes)
d <- data[,names(data) %in% c("eigenvalue2", "density", "determinant")]
scatterplot3d(d, angle = 10)
library(plotly)
Registered S3 method overwritten by 'data.table':
  method           from
  print.data.table     

Attaching package: ‘plotly’

The following object is masked from ‘package:latex2exp’:

    TeX

The following object is masked from ‘package:ggplot2’:

    last_plot

The following object is masked from ‘package:igraph’:

    groups

The following object is masked from ‘package:stats’:

    filter

The following object is masked from ‘package:graphics’:

    layout
mtcars$am[which(mtcars$am == 0)] <- 'Automatic'
mtcars$am[which(mtcars$am == 1)] <- 'Manual'
mtcars$am <- as.factor(mtcars$am)

d <- data[sample(1:nrow(data), 1000),]

fig <- plot_ly(d, x = ~determinant, y = ~density, z = ~eigenvalue2)
fig <- fig %>% add_markers(size = 1)
fig <- fig %>% layout(scene = list(xaxis = list(title = 'Weight'),
                     yaxis = list(title = 'Gross horsepower'),
                     zaxis = list(title = '1/4 mile time')))

fig
`arrange_()` is deprecated as of dplyr 0.7.0.
Please use `arrange()` instead.
See vignette('programming') for more help
This warning is displayed once every 8 hours.
Call `lifecycle::last_warnings()` to see where this warning was generated.

OK so nothing great, well the spread is heteroskedastic so let’s log transform it:

ggplot(data, aes(x = density, y = log(eigenvalue2))) +
  geom_point(mapping = aes(size = size, color = p, shape = factor(n))) +
#  stat_smooth() +
  scale_size_continuous(range = c(0.1,1.5)) +
  labs(x = "Density of Adjacency Matrix", y = "Second Eigenvalue of Power Walk Transition Probability Matrix")

We could probably model this with a quadratic:

mod_x1 <- lm(log(eigenvalue2) ~ poly(density, 1), data = data)
data$x1 <- predict(mod_x1)

mod_x2 <- lm(log(eigenvalue2) ~ poly(density, 2), data = data)
data$x2 <- predict(mod_x2)

mod_x3 <- lm(log(eigenvalue2) ~ poly(density, 3), data = data)
data$x3 <- predict(mod_x3)

mod_x4 <- lm(log(eigenvalue2) ~ poly(density, 4), data = data)
data$x4 <- predict(mod_x4)

mod_x5 <- lm(log(eigenvalue2) ~ poly(density, 5), data = data)
data$x5 <- predict(mod_x5)

mod_x5 <- lm(log(eigenvalue2) ~ poly(density, 5), data = data)
data$x5 <- predict(mod_x5)

mod_x6 <- lm(log(eigenvalue2) ~ poly(density, 6), data = data)
data$x6 <- predict(mod_x6)


mod_xl <- lm(log(eigenvalue2) ~ log(1-density), data = data)
data$xl <- predict(mod_xl)
max(mod_xl$residuals)*2
[1] 0.8245406
# TODO Change the colour of each model by using pivot_longer
# TODO Make a plot of degree vs RSS, comment that the lack of elbo is evidence to regect
# TODO Try a negative log, any luck? with that
# TODO Does this vary by beta?
# TODO Write it up in a report
# DONE What about a sqrt transform and then a linear model?
  # Leaves too much variance
ggplot(data, aes(x = density, y = log(eigenvalue2))) +
  geom_point(mapping = aes(size = size, alpha = 0.01,  color = size, shape = factor(n))) +
#  stat_smooth() +
  scale_size_continuous(range = c(0.1,1.5)) +
  labs(x = "Density of Adjacency Matrix [ mean(A) ]", y = TeX("$\\log\\left( \\xi_2 \\right)$ of T")) +
  geom_line(aes(x = density, y = x1, lwd = 2)) +
  geom_line(aes(x = density, y = xl, lwd = 3)) 

#  geom_line(aes(x = density, y = x3, lwd = 0.5)) +
#  geom_line(aes(x = density, y = x4, lwd = 0.5)) +
#  geom_line(aes(x = density, y = x5, lwd = 0.5)) +
# geom_line(aes(x = density, y = x6, lwd = 36)) 

Look at the Trace of T

ggplot(data, aes(x = trace_w , y = log(eigenvalue2))) +
  geom_point(mapping = aes(size = size, color = p, shape = factor(n))) +
#  stat_smooth() +
  scale_size_continuous(range = c(0.1,1.5)) +
  labs(x = "Trace of Transition Matrix", y = TeX("$\\log\\left( \\xi_2 \\right)$ of \\mathbf{W}"))

mod_df <- data

mod_hyp <- lm(log(eigenvalue2) ~ I(trace_w^(-1)), data = data)
mod_df$hyp <- predict(mod_hyp)

mod_log <- lm(log(eigenvalue2) ~ log(trace_w), data = data)
mod_df$log <- predict(mod_log)
ggplot(mod_df, aes(x = trace_w, y = log(eigenvalue2))) +
  geom_point(mapping = aes(size = size, alpha = 0.01,  color = size, shape = factor(n))) +
#  stat_smooth() +
  scale_size_continuous(range = c(0.1,1.5)) +
  labs(x = "Trace of A", y = TeX("$\\log\\left( \\xi_2 \\right)$ of T")) +
  geom_line(aes(x = trace_w, y = hyp, lwd = 2)) +
  geom_line(aes(x = trace_w, y = log, lwd = 2))

mod_df_long <- pivot_longer(mod_df, cols = c(hyp, log), names_to = "Model_Type", values_to = "eigenvalue2_mod")
mod_df_long$eigenvalue2_log <- log(mod_df_long$eigenvalue2)

ggplot(mod_df_long, aes(x = trace_w)) +
  geom_point(shape = 23, aes(y = eigenvalue2_log), fill = "lightblue", col = "black", size = 0.7, alpha = 0.4) +
  geom_line(aes(y = eigenvalue2_mod, col = Model_Type), size = 1) +
  labs(col = c("Model \nType")) +
  scale_color_manual(labels = c("Hyperbolic", "Logarithmic"),
                     values = c("indianred", "royalblue")) +
  theme_linedraw()

Model Chi Distribution

NOPE


chival <- dchisq(seq(from = 0, to = 40, length.out = 100), df = 10)*7
index  <- seq(from = 0, to = 2.2, length.out = 100)
chidata  <- data.frame(index = index, chi = chival)
ggplot(data) +
  geom_point(mapping = aes(x = density, y = eigenvalue2, size = beta, color = size, shape = factor(n))) +
  geom_line(data = chidata, mapping = aes(x = index, y = chi)) +
  scale_size_continuous(range = c(0.1,1)) +
  labs(x = "Density of Adjacency Matrix", y = "Second Eigenvalue of Power Walk Transition Probability Matrix")

Looking at Determinant

constants:

n <- 20
p <- 1:n/n
beta <- 1:n/n
beta <- runif(n)*100
sz <- ((1:n)/n)*100+10
input_var <- expand.grid("n" = n, "p" = p, "beta" = beta, "size" = sz)

functions:

random_graph <- function(n, p, beta, size) {
      g1 <- igraph::erdos.renyi.game(n = sz, p)
      A <- igraph::get.adjacency(g1) # Row to column
      A <- Matrix::t(A)

      A_dens <- mean(A)
      T      <- PageRank::power_walk_prob_trans(A)
      e2     <- eigen(T, only.values = TRUE)$values[2] # R orders by descending magnitude
      A_det  <- det(A)
      return(c(abs(abs(e2)-0.4), abs(A_det), A_dens))
}

Map the function

nc <- length(random_graph(1, 1, 1, 1))
Y <- matrix(ncol = nc, nrow = nrow(input_var))
for (i in 1:nrow(input_var)) {
  X <- as.vector(input_var[i,])
  Y[i,] <-  random_graph(X$n, X$p, X$beta, X$size)
}
if (sum(abs(Y) != abs(Re(Y))) == 0) {
  Y <- Re(Y)
}
nrow(input_var)
nrow(Y)
Y <- as.data.frame(Y); colnames(Y) <- c("eigenvalue2", "determinant")
data <- cbind(input_var, Y)
ggplot(data) +
  geom_point(mapping = aes(x = determinant, y = eigenvalue2, size = size, color = beta, shape = factor(n))) +
  scale_size_continuous(range = c(0.1,1)) +
  labs(y = "||e2|-0.4|", x = TeX("$\\left\\lvert A \\right\\rvert $"))
g1 <- igraph::erdos.renyi.game(n = sz, p)
coords <- layout_with_fr(g1, dim = 3)
# plot(g1)
rglplot(g1, layout=coords, size = 0.1)

## Not run: 
g <- make_lattice( c(5,5,5) )
coords <- layout_with_fr(g, dim=3)
rglplot(g, layout=coords)

## End(Not run)
n <- sz <- size <-  10^3
p <- 0.
g1 <- igraph::erdos.renyi.game(n = sz, p)
A <- igraph::get.adjacency(g1) # Row to column
A <- Matrix::t(A)
det(A)
ggplot(data) +
  geom_point(mapping = aes(x = size, y = determinant, size = size, color = beta, shape = factor(n))) +
  scale_size_continuous(range = c(0.1,1)) +
  labs(x = "size", y = "determinant")

Get Different Data

constants:

n <- 10
p <- 1:n/n
beta <- 1:n/n
beta <- runif(n)*100
sz <- 1:n/n+100
input_var <- expand.grid("n" = n, "p" = p, "beta" = beta, "size" = sz)

functions:

random_graph <- function(n, p, beta, size) {
      g1 <- igraph::erdos.renyi.game(n = sz, p)
      A <- igraph::get.adjacency(g1) # Row to column
      A <- Matrix::t(A)

      A_dens <- mean(A)
      T      <- PageRank::power_walk_prob_trans(A)
      e2     <- eigen(T, only.values = TRUE)$values[2] # R orders by descending magnitude
      A_det  <- det(A)
      return(c(abs(e2), A_det, A_dens))
}

Map the function

nc <- length(random_graph(1, 1, 1, 1))
Y <- matrix(ncol = nc, nrow = nrow(input_var))
for (i in 1:nrow(input_var)) {
  X <- as.vector(input_var[i,])
  Y[i,] <-  random_graph(X$n, X$p, X$beta, X$size)
}
if (sum(abs(Y) != abs(Re(Y))) == 0) {
  Y <- Re(Y)
}
nrow(input_var)
nrow(Y)
Y <- as.data.frame(Y); colnames(Y) <- c("eigenvalue2", "determinant")
data <- cbind(input_var, Y)

chival <- dchisq(seq(from = 0, to = 40, length.out = 100), df = 10)*7
index  <- seq(from = 0, to = 2.2, length.out = 100)
chidata  <- data.frame(index = index, chi = chival)
ggplot(data) +
  geom_point(mapping = aes(x = determinant, y = eigenvalue2, size = size, color = beta, shape = factor(n))) +
  scale_size_continuous(range = c(0.1,1)) +
  labs(x = "Density of Adjacency Matrix", y = "Second Eigenvalue of Power Walk Transition Probability Matrix")
g1 <- igraph::erdos.renyi.game(n = sz, p)
coords <- layout_with_fr(g1, dim = 3)
# plot(g1)
# rglplot(g1, layout=coords, size = 0.1)

## Not run: 
g <- make_lattice( c(5,5,5) )
coords <- layout_with_fr(g, dim=3)
rglplot(g, layout=coords)

## End(Not run)
n <- sz <- size <-  100
p <- 0.4
g1 <- igraph::erdos.renyi.game(n = sz, p)
A <- igraph::get.adjacency(g1) # Row to column
A <- Matrix::t(A)
det(A)
LS0tCnRpdGxlOiAiSW52ZXN0aWdhdGluZyBTZWNvbmQgRWlnZW52YWx1ZSIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKIyBJbnZlc3RpZ2F0aW5nIFNlY29uZCBFaWdlbnZhbHVlCgpgYGB7cn0KICBpZiAocmVxdWlyZSgiUGFnZVJhbmsiKSkgewogICAgICBsaWJyYXJ5KFBhZ2VSYW5rKQogICAgfWVsc2V7CiAgICAgIGRldnRvb2xzOjppbnN0YWxsX2dpdGh1YigicnlhbmdyZWVudXAvUGFnZVJhbmsiKQogICAgICBsaWJyYXJ5KFBhZ2VSYW5rKQogICAgfQoKICBsaWJyYXJ5KHBhY21hbikKICBwYWNtYW46OnBfbG9hZChQYWdlUmFuaywgZGV2dG9vbHMsIE1hdHJpeCwgaWdyYXBoLCBtaXNlLCB0aWR5dmVyc2UsIHJnbCwgbGF0ZXgyZXhwKQojICBtaXNlKCkKYGBgCgoKCiMjIExvb2tpbmcgYXQgRGVuc2l0eQoKIyMjIENvbnN0YW50cwoKRGVmaW5lIHNvbWUgY29uc3RhbnRzCgpgYGB7cn0KbiA8LSAyMApwIDwtIDE6bi9uCmJldGEgPC0gMTpuL24KYmV0YSA8LSBydW5pZihuKSoxMDAKI3N6IDwtIDE6bi9uKzEwCnN6IDwtICgxOm4vbikqMTAwKzEwCmlucHV0X3ZhciA8LSBleHBhbmQuZ3JpZCgibiIgPSBuLCAicCIgPSBwLCAiYmV0YSIgPSBiZXRhLCAic2l6ZSIgPSBzeikKaW5wdXRfdmFyCmBgYAoKIyMjIEZ1bmN0aW9uIHRvIEJ1aWxkIEdyYXBoCgpgYGB7cn0KcmFuZG9tX2dyYXBoIDwtIGZ1bmN0aW9uKG4sIHAsIGJldGEsIHNpemUpIHsKICAgICAgZzEgPC0gaWdyYXBoOjplcmRvcy5yZW55aS5nYW1lKG4gPSBzeiwgcCkKICAgICAgQSA8LSBpZ3JhcGg6OmdldC5hZGphY2VuY3koZzEpICMgUm93IHRvIGNvbHVtbgogICAgICBBIDwtIE1hdHJpeDo6dChBKQoKICAgICAgQV9kZW5zIDwtIG1lYW4oQSkKICAgICAgVCAgICAgIDwtIFBhZ2VSYW5rOjpwb3dlcl93YWxrX3Byb2JfdHJhbnMoQSkKICAgICAgdHIgICAgIDwtIHN1bShkaWFnKFQpKQogICAgICBlMiAgICAgPC0gZWlnZW4oVCwgb25seS52YWx1ZXMgPSBUUlVFKSR2YWx1ZXNbMl0gIyBSIG9yZGVycyBieSBkZXNjZW5kaW5nIG1hZ25pdHVkZQogICAgICBBX2RldCAgPC0gZGV0KFQpCiAgICAgIHJldHVybihjKGFicyhlMiksIEFfZGVucywgQV9kZXQsIHRyKSkKfQpgYGAKCiMjIyBSZXR1cm4gcmVzdWx0cwoKTWFwIHRoZSBmdW5jdGlvbgoKYGBge3J9Cm5jIDwtIGxlbmd0aChyYW5kb21fZ3JhcGgoMSwgMSwgMSwgMSkpClkgPC0gbWF0cml4KG5jb2wgPSBuYywgbnJvdyA9IG5yb3coaW5wdXRfdmFyKSkKZm9yIChpIGluIDE6bnJvdyhpbnB1dF92YXIpKSB7CiAgWCA8LSBhcy52ZWN0b3IoaW5wdXRfdmFyW2ksXSkKICBZW2ksXSA8LSAgcmFuZG9tX2dyYXBoKFgkbiwgWCRwLCBYJGJldGEsIFgkc2l6ZSkKfQppZiAoc3VtKGFicyhZKSAhPSBhYnMoUmUoWSkpKSA9PSAwKSB7CiAgWSA8LSBSZShZKQp9Cm5yb3coaW5wdXRfdmFyKQpucm93KFkpClkgPC0gYXMuZGF0YS5mcmFtZShZKTsgY29sbmFtZXMoWSkgPC0gYygiZWlnZW52YWx1ZTIiLCAiZGVuc2l0eSIsICJkZXRlcm1pbmFudCIsICJ0cmFjZV93IikKKGRhdGEgPC0gY2JpbmQoaW5wdXRfdmFyLCBZKSkgJT4lIGhlYWQoKQpkYXRhIDwtIGRhdGFbZGF0YSRkZW5zaXR5IT0wLF0KCmBgYAoKCiMjIyBQbG90IFJlc3VsdHMKCgpgYGB7cn0KCmNoaXZhbCA8LSBkY2hpc3Eoc2VxKGZyb20gPSAwLCB0byA9IDQwLCBsZW5ndGgub3V0ID0gMTAwKSwgZGYgPSAxMCkqNwppbmRleCAgPC0gc2VxKGZyb20gPSAwLCB0byA9IDIuMiwgbGVuZ3RoLm91dCA9IDEwMCkKY2hpZGF0YSAgPC0gZGF0YS5mcmFtZShpbmRleCA9IGluZGV4LCBjaGkgPSBjaGl2YWwpCmdncGxvdChkYXRhKSArCiAgZ2VvbV9wb2ludChtYXBwaW5nID0gYWVzKHggPSBkZW5zaXR5LCB5ID0gZWlnZW52YWx1ZTIsIHNpemUgPSBiZXRhLCBjb2xvciA9IHNpemUsIHNoYXBlID0gZmFjdG9yKG4pKSkgKwogIHNjYWxlX3NpemVfY29udGludW91cyhyYW5nZSA9IGMoMC4xLDEpKSArCiAgbGFicyh4ID0gIkRlbnNpdHkgb2YgQWRqYWNlbmN5IE1hdHJpeCIsIHkgPSBUZVgoIiRcXHhpXzIkIG9mICRUX3tQV30kIikpCmBgYAoKYGBge3J9Cm1vZCA8LSBsbShlaWdlbnZhbHVlMiB+IHBvbHkoZGVuc2l0eSwgMSksIGRhdGEgPSBkYXRhKQptb2QkcmVzaWR1YWxzICU+JSAgaGlzdChicmVha3MgPSA5MCkKaGlzdChybm9ybSgzMDAwKSwgYnJlYWtzID0gMTAwKQpwbG90KG1vZCkKCmBgYAoKClRoaXMgaXMgaW50ZXJlc3RpbmcsIGxldHMgbG9vayBhdCBhIHNuYXBzaG90IG9mIGl0OgoKYGBge3J9CnBhaXJzKGRhdGEpCmNvcihkYXRhKQpsaWJyYXJ5KGNvcnJwbG90KQpjb3JycGxvdChjb3IoZGF0YSksIG1ldGhvZCA9ICJlbGxpcHNlIiwgdHlwZSA9ICJsb3dlciIpCm5hbWVzKGRhdGEpCmBgYAoKYGBge3J9CmxpYnJhcnkoc2NhdHRlcnBsb3QzZCkKc2hhcGVzID0gYygxNiwgMTcsIDE4KSAKc2hhcGVzIDwtIHNoYXBlc1thcy5udW1lcmljKGlyaXMkU3BlY2llcyldCnNjYXR0ZXJwbG90M2QoaXJpc1ssMTozXSwgcGNoID0gc2hhcGVzKQpgYGAKYGBge3J9CmQgPC0gZGF0YVssbmFtZXMoZGF0YSkgJWluJSBjKCJlaWdlbnZhbHVlMiIsICJkZW5zaXR5IiwgImRldGVybWluYW50IildCnNjYXR0ZXJwbG90M2QoZCwgYW5nbGUgPSAxMCkKYGBgCmBgYHtyfQpsaWJyYXJ5KHBsb3RseSkKCm10Y2FycyRhbVt3aGljaChtdGNhcnMkYW0gPT0gMCldIDwtICdBdXRvbWF0aWMnCm10Y2FycyRhbVt3aGljaChtdGNhcnMkYW0gPT0gMSldIDwtICdNYW51YWwnCm10Y2FycyRhbSA8LSBhcy5mYWN0b3IobXRjYXJzJGFtKQoKZCA8LSBkYXRhW3NhbXBsZSgxOm5yb3coZGF0YSksIDEwMDApLF0KCmZpZyA8LSBwbG90X2x5KGQsIHggPSB+ZGV0ZXJtaW5hbnQsIHkgPSB+ZGVuc2l0eSwgeiA9IH5laWdlbnZhbHVlMikKZmlnIDwtIGZpZyAlPiUgYWRkX21hcmtlcnMoc2l6ZSA9IDEpCmZpZyA8LSBmaWcgJT4lIGxheW91dChzY2VuZSA9IGxpc3QoeGF4aXMgPSBsaXN0KHRpdGxlID0gJ1dlaWdodCcpLAogICAgICAgICAgICAgICAgICAgICB5YXhpcyA9IGxpc3QodGl0bGUgPSAnR3Jvc3MgaG9yc2Vwb3dlcicpLAogICAgICAgICAgICAgICAgICAgICB6YXhpcyA9IGxpc3QodGl0bGUgPSAnMS80IG1pbGUgdGltZScpKSkKCmZpZwoKYGBgCgoKCgpPSyBzbyBub3RoaW5nIGdyZWF0LCB3ZWxsIHRoZSBzcHJlYWQgaXMgaGV0ZXJvc2tlZGFzdGljIHNvIGxldCdzIGxvZyB0cmFuc2Zvcm0gaXQ6CgoKCmBgYHtyfQpnZ3Bsb3QoZGF0YSwgYWVzKHggPSBkZW5zaXR5LCB5ID0gbG9nKGVpZ2VudmFsdWUyKSkpICsKICBnZW9tX3BvaW50KG1hcHBpbmcgPSBhZXMoc2l6ZSA9IHNpemUsIGNvbG9yID0gcCwgc2hhcGUgPSBmYWN0b3IobikpKSArCiMgIHN0YXRfc21vb3RoKCkgKwogIHNjYWxlX3NpemVfY29udGludW91cyhyYW5nZSA9IGMoMC4xLDEuNSkpICsKICBsYWJzKHggPSAiRGVuc2l0eSBvZiBBZGphY2VuY3kgTWF0cml4IiwgeSA9ICJTZWNvbmQgRWlnZW52YWx1ZSBvZiBQb3dlciBXYWxrIFRyYW5zaXRpb24gUHJvYmFiaWxpdHkgTWF0cml4IikKYGBgCgpXZSBjb3VsZCBwcm9iYWJseSBtb2RlbCB0aGlzIHdpdGggYSBxdWFkcmF0aWM6CgpgYGB7cn0KbW9kX3gxIDwtIGxtKGxvZyhlaWdlbnZhbHVlMikgfiBwb2x5KGRlbnNpdHksIDEpLCBkYXRhID0gZGF0YSkKZGF0YSR4MSA8LSBwcmVkaWN0KG1vZF94MSkKCm1vZF94MiA8LSBsbShsb2coZWlnZW52YWx1ZTIpIH4gcG9seShkZW5zaXR5LCAyKSwgZGF0YSA9IGRhdGEpCmRhdGEkeDIgPC0gcHJlZGljdChtb2RfeDIpCgptb2RfeDMgPC0gbG0obG9nKGVpZ2VudmFsdWUyKSB+IHBvbHkoZGVuc2l0eSwgMyksIGRhdGEgPSBkYXRhKQpkYXRhJHgzIDwtIHByZWRpY3QobW9kX3gzKQoKbW9kX3g0IDwtIGxtKGxvZyhlaWdlbnZhbHVlMikgfiBwb2x5KGRlbnNpdHksIDQpLCBkYXRhID0gZGF0YSkKZGF0YSR4NCA8LSBwcmVkaWN0KG1vZF94NCkKCm1vZF94NSA8LSBsbShsb2coZWlnZW52YWx1ZTIpIH4gcG9seShkZW5zaXR5LCA1KSwgZGF0YSA9IGRhdGEpCmRhdGEkeDUgPC0gcHJlZGljdChtb2RfeDUpCgptb2RfeDUgPC0gbG0obG9nKGVpZ2VudmFsdWUyKSB+IHBvbHkoZGVuc2l0eSwgNSksIGRhdGEgPSBkYXRhKQpkYXRhJHg1IDwtIHByZWRpY3QobW9kX3g1KQoKbW9kX3g2IDwtIGxtKGxvZyhlaWdlbnZhbHVlMikgfiBwb2x5KGRlbnNpdHksIDYpLCBkYXRhID0gZGF0YSkKZGF0YSR4NiA8LSBwcmVkaWN0KG1vZF94NikKCgptb2RfeGwgPC0gbG0obG9nKGVpZ2VudmFsdWUyKSB+IGxvZygxLWRlbnNpdHkpLCBkYXRhID0gZGF0YSkKZGF0YSR4bCA8LSBwcmVkaWN0KG1vZF94bCkKbWF4KG1vZF94bCRyZXNpZHVhbHMpKjIKYGBgCgpgYGB7cn0KIyBUT0RPIENoYW5nZSB0aGUgY29sb3VyIG9mIGVhY2ggbW9kZWwgYnkgdXNpbmcgcGl2b3RfbG9uZ2VyCiMgVE9ETyBNYWtlIGEgcGxvdCBvZiBkZWdyZWUgdnMgUlNTLCBjb21tZW50IHRoYXQgdGhlIGxhY2sgb2YgZWxibyBpcyBldmlkZW5jZSB0byByZWdlY3QKIyBUT0RPIFRyeSBhIG5lZ2F0aXZlIGxvZywgYW55IGx1Y2s/IHdpdGggdGhhdAojIFRPRE8gRG9lcyB0aGlzIHZhcnkgYnkgYmV0YT8KIyBUT0RPIFdyaXRlIGl0IHVwIGluIGEgcmVwb3J0CiMgRE9ORSBXaGF0IGFib3V0IGEgc3FydCB0cmFuc2Zvcm0gYW5kIHRoZW4gYSBsaW5lYXIgbW9kZWw/CiAgIyBMZWF2ZXMgdG9vIG11Y2ggdmFyaWFuY2UKZ2dwbG90KGRhdGEsIGFlcyh4ID0gZGVuc2l0eSwgeSA9IGxvZyhlaWdlbnZhbHVlMikpKSArCiAgZ2VvbV9wb2ludChtYXBwaW5nID0gYWVzKHNpemUgPSBzaXplLCBhbHBoYSA9IDAuMDEsICBjb2xvciA9IHNpemUsIHNoYXBlID0gZmFjdG9yKG4pKSkgKwojICBzdGF0X3Ntb290aCgpICsKICBzY2FsZV9zaXplX2NvbnRpbnVvdXMocmFuZ2UgPSBjKDAuMSwxLjUpKSArCiAgbGFicyh4ID0gIkRlbnNpdHkgb2YgQWRqYWNlbmN5IE1hdHJpeCBbIG1lYW4oQSkgXSIsIHkgPSBUZVgoIiRcXGxvZ1xcbGVmdCggXFx4aV8yIFxccmlnaHQpJCBvZiBUIikpICsKICBnZW9tX2xpbmUoYWVzKHggPSBkZW5zaXR5LCB5ID0geDEsIGx3ZCA9IDIpKSArCiAgZ2VvbV9saW5lKGFlcyh4ID0gZGVuc2l0eSwgeSA9IHhsLCBsd2QgPSAzKSkgCiMgIGdlb21fbGluZShhZXMoeCA9IGRlbnNpdHksIHkgPSB4MywgbHdkID0gMC41KSkgKwojICBnZW9tX2xpbmUoYWVzKHggPSBkZW5zaXR5LCB5ID0geDQsIGx3ZCA9IDAuNSkpICsKIyAgZ2VvbV9saW5lKGFlcyh4ID0gZGVuc2l0eSwgeSA9IHg1LCBsd2QgPSAwLjUpKSArCiMgZ2VvbV9saW5lKGFlcyh4ID0gZGVuc2l0eSwgeSA9IHg2LCBsd2QgPSAzNikpIAoKCgpgYGAKIyMjIyBMb29rIGF0IHRoZSBUcmFjZSBvZiBUCgpgYGB7cn0KZ2dwbG90KGRhdGEsIGFlcyh4ID0gdHJhY2VfdyAsIHkgPSBsb2coZWlnZW52YWx1ZTIpKSkgKwogIGdlb21fcG9pbnQobWFwcGluZyA9IGFlcyhzaXplID0gc2l6ZSwgY29sb3IgPSBwLCBzaGFwZSA9IGZhY3RvcihuKSkpICsKIyAgc3RhdF9zbW9vdGgoKSArCiAgc2NhbGVfc2l6ZV9jb250aW51b3VzKHJhbmdlID0gYygwLjEsMS41KSkgKwogIGxhYnMoeCA9ICJUcmFjZSBvZiBUcmFuc2l0aW9uIE1hdHJpeCIsIHkgPSBUZVgoIiRcXGxvZ1xcbGVmdCggXFx4aV8yIFxccmlnaHQpJCBvZiBcXG1hdGhiZntXfSIpKQpgYGAKCmBgYHtyfQptb2RfZGYgPC0gZGF0YQoKbW9kX2h5cCA8LSBsbShsb2coZWlnZW52YWx1ZTIpIH4gSSh0cmFjZV93XigtMSkpLCBkYXRhID0gZGF0YSkKbW9kX2RmJGh5cCA8LSBwcmVkaWN0KG1vZF9oeXApCgptb2RfbG9nIDwtIGxtKGxvZyhlaWdlbnZhbHVlMikgfiBsb2codHJhY2VfdyksIGRhdGEgPSBkYXRhKQptb2RfZGYkbG9nIDwtIHByZWRpY3QobW9kX2xvZykKCmBgYAoKYGBge3J9CmdncGxvdChtb2RfZGYsIGFlcyh4ID0gdHJhY2VfdywgeSA9IGxvZyhlaWdlbnZhbHVlMikpKSArCiAgZ2VvbV9wb2ludChtYXBwaW5nID0gYWVzKHNpemUgPSBzaXplLCBhbHBoYSA9IDAuMDEsICBjb2xvciA9IHNpemUsIHNoYXBlID0gZmFjdG9yKG4pKSkgKwojICBzdGF0X3Ntb290aCgpICsKICBzY2FsZV9zaXplX2NvbnRpbnVvdXMocmFuZ2UgPSBjKDAuMSwxLjUpKSArCiAgbGFicyh4ID0gIlRyYWNlIG9mIEEiLCB5ID0gVGVYKCIkXFxsb2dcXGxlZnQoIFxceGlfMiBcXHJpZ2h0KSQgb2YgVCIpKSArCiAgZ2VvbV9saW5lKGFlcyh4ID0gdHJhY2VfdywgeSA9IGh5cCwgbHdkID0gMikpICsKICBnZW9tX2xpbmUoYWVzKHggPSB0cmFjZV93LCB5ID0gbG9nLCBsd2QgPSAyKSkKYGBgCgpgYGB7cn0KbW9kX2RmX2xvbmcgPC0gcGl2b3RfbG9uZ2VyKG1vZF9kZiwgY29scyA9IGMoaHlwLCBsb2cpLCBuYW1lc190byA9ICJNb2RlbF9UeXBlIiwgdmFsdWVzX3RvID0gImVpZ2VudmFsdWUyX21vZCIpCm1vZF9kZl9sb25nJGVpZ2VudmFsdWUyX2xvZyA8LSBsb2cobW9kX2RmX2xvbmckZWlnZW52YWx1ZTIpCgpnZ3Bsb3QobW9kX2RmX2xvbmcsIGFlcyh4ID0gdHJhY2VfdykpICsKICBnZW9tX3BvaW50KHNoYXBlID0gMjMsIGFlcyh5ID0gZWlnZW52YWx1ZTJfbG9nKSwgZmlsbCA9ICJsaWdodGJsdWUiLCBjb2wgPSAiYmxhY2siLCBzaXplID0gMC43LCBhbHBoYSA9IDAuNCkgKwogIGdlb21fbGluZShhZXMoeSA9IGVpZ2VudmFsdWUyX21vZCwgY29sID0gTW9kZWxfVHlwZSksIHNpemUgPSAxKSArCiAgbGFicyhjb2wgPSBjKCJNb2RlbCBcblR5cGUiKSkgKwogIHNjYWxlX2NvbG9yX21hbnVhbChsYWJlbHMgPSBjKCJIeXBlcmJvbGljIiwgIkxvZ2FyaXRobWljIiksCiAgICAgICAgICAgICAgICAgICAgIHZhbHVlcyA9IGMoImluZGlhbnJlZCIsICJyb3lhbGJsdWUiKSkgKwogIHRoZW1lX2xpbmVkcmF3KCkKYGBgCgoKCgojIyMjIE1vZGVsIENoaSBEaXN0cmlidXRpb24KCk5PUEUKCmBgYHtyfQoKY2hpdmFsIDwtIGRjaGlzcShzZXEoZnJvbSA9IDAsIHRvID0gNDAsIGxlbmd0aC5vdXQgPSAxMDApLCBkZiA9IDEwKSo3CmluZGV4ICA8LSBzZXEoZnJvbSA9IDAsIHRvID0gMi4yLCBsZW5ndGgub3V0ID0gMTAwKQpjaGlkYXRhICA8LSBkYXRhLmZyYW1lKGluZGV4ID0gaW5kZXgsIGNoaSA9IGNoaXZhbCkKZ2dwbG90KGRhdGEpICsKICBnZW9tX3BvaW50KG1hcHBpbmcgPSBhZXMoeCA9IGRlbnNpdHksIHkgPSBlaWdlbnZhbHVlMiwgc2l6ZSA9IGJldGEsIGNvbG9yID0gc2l6ZSwgc2hhcGUgPSBmYWN0b3IobikpKSArCiAgZ2VvbV9saW5lKGRhdGEgPSBjaGlkYXRhLCBtYXBwaW5nID0gYWVzKHggPSBpbmRleCwgeSA9IGNoaSkpICsKICBzY2FsZV9zaXplX2NvbnRpbnVvdXMocmFuZ2UgPSBjKDAuMSwxKSkgKwogIGxhYnMoeCA9ICJEZW5zaXR5IG9mIEFkamFjZW5jeSBNYXRyaXgiLCB5ID0gIlNlY29uZCBFaWdlbnZhbHVlIG9mIFBvd2VyIFdhbGsgVHJhbnNpdGlvbiBQcm9iYWJpbGl0eSBNYXRyaXgiKQoKYGBgCgoKCiMjIExvb2tpbmcgYXQgRGV0ZXJtaW5hbnQKCgpjb25zdGFudHM6CgpgYGB7cn0KbiA8LSAyMApwIDwtIDE6bi9uCmJldGEgPC0gMTpuL24KYmV0YSA8LSBydW5pZihuKSoxMDAKc3ogPC0gKCgxOm4pL24pKjEwMCsxMAppbnB1dF92YXIgPC0gZXhwYW5kLmdyaWQoIm4iID0gbiwgInAiID0gcCwgImJldGEiID0gYmV0YSwgInNpemUiID0gc3opCmBgYAoKZnVuY3Rpb25zOgoKYGBge3J9CnJhbmRvbV9ncmFwaCA8LSBmdW5jdGlvbihuLCBwLCBiZXRhLCBzaXplKSB7CiAgICAgIGcxIDwtIGlncmFwaDo6ZXJkb3MucmVueWkuZ2FtZShuID0gc3osIHApCiAgICAgIEEgPC0gaWdyYXBoOjpnZXQuYWRqYWNlbmN5KGcxKSAjIFJvdyB0byBjb2x1bW4KICAgICAgQSA8LSBNYXRyaXg6OnQoQSkKCiAgICAgIEFfZGVucyA8LSBtZWFuKEEpCiAgICAgIFQgICAgICA8LSBQYWdlUmFuazo6cG93ZXJfd2Fsa19wcm9iX3RyYW5zKEEpCiAgICAgIGUyICAgICA8LSBlaWdlbihULCBvbmx5LnZhbHVlcyA9IFRSVUUpJHZhbHVlc1syXSAjIFIgb3JkZXJzIGJ5IGRlc2NlbmRpbmcgbWFnbml0dWRlCiAgICAgIEFfZGV0ICA8LSBkZXQoQSkKICAgICAgcmV0dXJuKGMoYWJzKGFicyhlMiktMC40KSwgYWJzKEFfZGV0KSwgQV9kZW5zKSkKfQpgYGAKCk1hcCB0aGUgZnVuY3Rpb24KCmBgYHtyfQpuYyA8LSBsZW5ndGgocmFuZG9tX2dyYXBoKDEsIDEsIDEsIDEpKQpZIDwtIG1hdHJpeChuY29sID0gbmMsIG5yb3cgPSBucm93KGlucHV0X3ZhcikpCmZvciAoaSBpbiAxOm5yb3coaW5wdXRfdmFyKSkgewogIFggPC0gYXMudmVjdG9yKGlucHV0X3ZhcltpLF0pCiAgWVtpLF0gPC0gIHJhbmRvbV9ncmFwaChYJG4sIFgkcCwgWCRiZXRhLCBYJHNpemUpCn0KaWYgKHN1bShhYnMoWSkgIT0gYWJzKFJlKFkpKSkgPT0gMCkgewogIFkgPC0gUmUoWSkKfQpucm93KGlucHV0X3ZhcikKbnJvdyhZKQpZIDwtIGFzLmRhdGEuZnJhbWUoWSk7IGNvbG5hbWVzKFkpIDwtIGMoImVpZ2VudmFsdWUyIiwgImRldGVybWluYW50IikKZGF0YSA8LSBjYmluZChpbnB1dF92YXIsIFkpCgoKCmBgYAoKCgpgYGB7cn0KZ2dwbG90KGRhdGEpICsKICBnZW9tX3BvaW50KG1hcHBpbmcgPSBhZXMoeCA9IGRldGVybWluYW50LCB5ID0gZWlnZW52YWx1ZTIsIHNpemUgPSBzaXplLCBjb2xvciA9IGJldGEsIHNoYXBlID0gZmFjdG9yKG4pKSkgKwogIHNjYWxlX3NpemVfY29udGludW91cyhyYW5nZSA9IGMoMC4xLDEpKSArCiAgbGFicyh5ID0gInx8ZTJ8LTAuNHwiLCB4ID0gVGVYKCIkXFxsZWZ0XFxsdmVydCBBIFxccmlnaHRcXHJ2ZXJ0ICQiKSkKCmBgYAoKYGBge3J9CmcxIDwtIGlncmFwaDo6ZXJkb3MucmVueWkuZ2FtZShuID0gc3osIHApCmNvb3JkcyA8LSBsYXlvdXRfd2l0aF9mcihnMSwgZGltID0gMykKIyBwbG90KGcxKQpyZ2xwbG90KGcxLCBsYXlvdXQ9Y29vcmRzLCBzaXplID0gMC4xKQpgYGAKCgpgYGB7cn0KCiMjIE5vdCBydW46IApnIDwtIG1ha2VfbGF0dGljZSggYyg1LDUsNSkgKQpjb29yZHMgPC0gbGF5b3V0X3dpdGhfZnIoZywgZGltPTMpCnJnbHBsb3QoZywgbGF5b3V0PWNvb3JkcykKCiMjIEVuZChOb3QgcnVuKQoKCgpgYGAKCgpgYGB7cn0KbiA8LSBzeiA8LSBzaXplIDwtICAxMF4zCnAgPC0gMC4KZzEgPC0gaWdyYXBoOjplcmRvcy5yZW55aS5nYW1lKG4gPSBzeiwgcCkKQSA8LSBpZ3JhcGg6OmdldC5hZGphY2VuY3koZzEpICMgUm93IHRvIGNvbHVtbgpBIDwtIE1hdHJpeDo6dChBKQpkZXQoQSkKCmBgYAoKCmBgYHtyfQpnZ3Bsb3QoZGF0YSkgKwogIGdlb21fcG9pbnQobWFwcGluZyA9IGFlcyh4ID0gc2l6ZSwgeSA9IGRldGVybWluYW50LCBzaXplID0gc2l6ZSwgY29sb3IgPSBiZXRhLCBzaGFwZSA9IGZhY3RvcihuKSkpICsKICBzY2FsZV9zaXplX2NvbnRpbnVvdXMocmFuZ2UgPSBjKDAuMSwxKSkgKwogIGxhYnMoeCA9ICJzaXplIiwgeSA9ICJkZXRlcm1pbmFudCIpCgpgYGAKCgoKCgoKCgojIyBHZXQgRGlmZmVyZW50IERhdGEKCgpjb25zdGFudHM6CgpgYGB7cn0KbiA8LSAxMApwIDwtIDE6bi9uCmJldGEgPC0gMTpuL24KYmV0YSA8LSBydW5pZihuKSoxMDAKc3ogPC0gMTpuL24rMTAwCmlucHV0X3ZhciA8LSBleHBhbmQuZ3JpZCgibiIgPSBuLCAicCIgPSBwLCAiYmV0YSIgPSBiZXRhLCAic2l6ZSIgPSBzeikKYGBgCgpmdW5jdGlvbnM6CgpgYGB7cn0KcmFuZG9tX2dyYXBoIDwtIGZ1bmN0aW9uKG4sIHAsIGJldGEsIHNpemUpIHsKICAgICAgZzEgPC0gaWdyYXBoOjplcmRvcy5yZW55aS5nYW1lKG4gPSBzeiwgcCkKICAgICAgQSA8LSBpZ3JhcGg6OmdldC5hZGphY2VuY3koZzEpICMgUm93IHRvIGNvbHVtbgogICAgICBBIDwtIE1hdHJpeDo6dChBKQoKICAgICAgQV9kZW5zIDwtIG1lYW4oQSkKICAgICAgVCAgICAgIDwtIFBhZ2VSYW5rOjpwb3dlcl93YWxrX3Byb2JfdHJhbnMoQSkKICAgICAgZTIgICAgIDwtIGVpZ2VuKFQsIG9ubHkudmFsdWVzID0gVFJVRSkkdmFsdWVzWzJdICMgUiBvcmRlcnMgYnkgZGVzY2VuZGluZyBtYWduaXR1ZGUKICAgICAgQV9kZXQgIDwtIGRldChBKQogICAgICByZXR1cm4oYyhhYnMoZTIpLCBBX2RldCwgQV9kZW5zKSkKfQpgYGAKCk1hcCB0aGUgZnVuY3Rpb24KCmBgYHtyfQpuYyA8LSBsZW5ndGgocmFuZG9tX2dyYXBoKDEsIDEsIDEsIDEpKQpZIDwtIG1hdHJpeChuY29sID0gbmMsIG5yb3cgPSBucm93KGlucHV0X3ZhcikpCmZvciAoaSBpbiAxOm5yb3coaW5wdXRfdmFyKSkgewogIFggPC0gYXMudmVjdG9yKGlucHV0X3ZhcltpLF0pCiAgWVtpLF0gPC0gIHJhbmRvbV9ncmFwaChYJG4sIFgkcCwgWCRiZXRhLCBYJHNpemUpCn0KaWYgKHN1bShhYnMoWSkgIT0gYWJzKFJlKFkpKSkgPT0gMCkgewogIFkgPC0gUmUoWSkKfQpucm93KGlucHV0X3ZhcikKbnJvdyhZKQpZIDwtIGFzLmRhdGEuZnJhbWUoWSk7IGNvbG5hbWVzKFkpIDwtIGMoImVpZ2VudmFsdWUyIiwgImRldGVybWluYW50IikKZGF0YSA8LSBjYmluZChpbnB1dF92YXIsIFkpCgoKCmBgYAoKCgpgYGB7cn0KCmNoaXZhbCA8LSBkY2hpc3Eoc2VxKGZyb20gPSAwLCB0byA9IDQwLCBsZW5ndGgub3V0ID0gMTAwKSwgZGYgPSAxMCkqNwppbmRleCAgPC0gc2VxKGZyb20gPSAwLCB0byA9IDIuMiwgbGVuZ3RoLm91dCA9IDEwMCkKY2hpZGF0YSAgPC0gZGF0YS5mcmFtZShpbmRleCA9IGluZGV4LCBjaGkgPSBjaGl2YWwpCmdncGxvdChkYXRhKSArCiAgZ2VvbV9wb2ludChtYXBwaW5nID0gYWVzKHggPSBkZXRlcm1pbmFudCwgeSA9IGVpZ2VudmFsdWUyLCBzaXplID0gc2l6ZSwgY29sb3IgPSBiZXRhLCBzaGFwZSA9IGZhY3RvcihuKSkpICsKICBzY2FsZV9zaXplX2NvbnRpbnVvdXMocmFuZ2UgPSBjKDAuMSwxKSkgKwogIGxhYnMoeCA9ICJEZW5zaXR5IG9mIEFkamFjZW5jeSBNYXRyaXgiLCB5ID0gIlNlY29uZCBFaWdlbnZhbHVlIG9mIFBvd2VyIFdhbGsgVHJhbnNpdGlvbiBQcm9iYWJpbGl0eSBNYXRyaXgiKQoKYGBgCgpgYGB7cn0KZzEgPC0gaWdyYXBoOjplcmRvcy5yZW55aS5nYW1lKG4gPSBzeiwgcCkKY29vcmRzIDwtIGxheW91dF93aXRoX2ZyKGcxLCBkaW0gPSAzKQojIHBsb3QoZzEpCiMgcmdscGxvdChnMSwgbGF5b3V0PWNvb3Jkcywgc2l6ZSA9IDAuMSkKYGBgCgoKYGBge3J9CgojIyBOb3QgcnVuOiAKZyA8LSBtYWtlX2xhdHRpY2UoIGMoNSw1LDUpICkKY29vcmRzIDwtIGxheW91dF93aXRoX2ZyKGcsIGRpbT0zKQpyZ2xwbG90KGcsIGxheW91dD1jb29yZHMpCgojIyBFbmQoTm90IHJ1bikKCgoKYGBgCgoKYGBge3J9Cm4gPC0gc3ogPC0gc2l6ZSA8LSAgMTAwCnAgPC0gMC40CmcxIDwtIGlncmFwaDo6ZXJkb3MucmVueWkuZ2FtZShuID0gc3osIHApCkEgPC0gaWdyYXBoOjpnZXQuYWRqYWNlbmN5KGcxKSAjIFJvdyB0byBjb2x1bW4KQSA8LSBNYXRyaXg6OnQoQSkKZGV0KEEpCmBgYAoKCgo=